#include <bits/stdc++.h>
using namespace std;
#define int long long
int st[1000010];

void solve() {
    int n;
    cin >> n;
    if(st[n]) {
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

signed main() {
    for(int i = 2; i <= 1000; i++) {
        int t = 1 + i;
        int s = i * i;
        t += s; s *= i;
        while(t <= 1000000){
            st[t] = 1;
            t += s;
            s *= i;
        }
    }
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}